package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * 669. 修剪二叉搜索树
 * @author feizns
 * @since 2020/1/4
 */
public class TrimBST {

    public static void main(String[] args) {
        TreeNode node = trimBST(node(), 1, 2);
        System.out.println(node.val);
    }

    private static TreeNode node() {
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(0);
        ret.right = new TreeNode(2);
        return ret;
    }

    public static TreeNode trimBST(TreeNode root, int L, int R) {
        return trimLeft(trimRight(root, R), L);
    }

    private static TreeNode trimRight(TreeNode root, int R) {
        if ( root != null ) {
            if ( root.val > R ) {
                root.right = null;
                return trimRight(root.left, R);
            } else if ( root.val == R )
                root.right = null;
            else
                root.right = trimRight(root.right, R);
        }
        return root;
    }

    private static TreeNode trimLeft(TreeNode root, int L) {
        if ( root != null ) {
            if ( root.val < L ) {
                root.left = null;
                return trimLeft(root.right, L);
            } else if ( root.val == L )
                root.left = null;
            else
                root.left = trimLeft(root.left, L);
        }
        return root;
    }

}
